package com.zc.easy.No14;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @program: leetCode_Exercise
 * @author: zhangcong
 * @create: 2019-09-11 11:00
 * @description: 最长公共前缀
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * 如果不存在公共前缀，返回空字符串 ""。
 * 示例 1:
 * <p>
 * 输入: ["flower","flow","flight"]
 * 输出: "fl"
 * 示例 2:
 * <p>
 * 输入: ["dog","racecar","car"]
 * 输出: ""
 * 解释: 输入不存在公共前缀。
 * <p>
 * 说明:
 * 所有输入只包含小写字母 a-z 。
 **/
public class Solution {
    /**
     * 依次取出第一个字符串你的字符，循环与其他字符串相同index字符比较。
     *
     * @param strs
     * @return
     */
    public static String longestCommonPrefix(String[] strs) {
        if (strs.length == 0 || strs[0].length() == 0) {
            return "";
        }
        Boolean loop = true;
        StringBuffer sb = new StringBuffer();
        int index = 0;
        while (loop) {
            char temp = strs[0].charAt(index);
            for (int i = 1; i < strs.length; i++) {
                if (strs[i].length() <= index || temp != strs[i].charAt(index)) {
                    loop = false;
                    break;
                }
            }
            if (loop) {
                sb.append(temp);
                index++;
            }
            if (strs[0].length() == index) {
                loop = false;
            }
        }
        return sb.toString();
    }


    public static String longestCommonPrefix1(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
       List<String> list=Arrays.stream(strs).sorted(Comparator.comparingInt(String::length)).collect(Collectors.toList());
        String str=list.get(0);
        if(str.length()==0){
            return "";
        }
        for(int i=str.length();i>=0;i--){
            String temp=str.substring(0,i);
            boolean isMatch=true;
            for (int j = 0; j < list.size(); j++) {
                if(list.get(j).indexOf(temp)!=0){
                    isMatch=false;
                    break;
                }
            }
            if(isMatch){
                return temp;
            }
        }
        return "";
    }

    public static void main(String[] args) {
        String[] str={"flower","flow","flight"};
//        String[] str = {"aa", "a"};
        System.out.println(longestCommonPrefix1(str));
    }
}
